Data availability
See also: Accumulator
Data availability proofs
On-chain (semi-non-interactive)
Towards on-chain non-interactive data availability proofs by Mustafa, 2018.12
On-Chain Non-Interactive Data Availability Proofs by John Adler, 2019.7
Non-interactive
Non-interactive data availability proofs by Mustafa, 2018.4
Erasure code
Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities
Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin
Availability and Validity @Web3 Foudation wiki
Video @Web3 Summit'19
Coded Merkle Tree: Solving Data Availability Attacks in Blockchains (eprint)
Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr (USC), Sreeram Kannan (University of Washington), Pramod Viswanath (UIUC)
FC'20
Background: Erasure coding for data invalidity/unavailability attack in light client/sharding (Al-bassam et al.)
Contribution: Propose SPAR protocol
A new hash accumulator named coded Merkle tree (CMT), which encodes every layer of the tree to protect the availability of the entire tree. This way, the Merkle proof of every coded symbol will be available, which will enable every parity equation to be committed and verified alone
https://gyazo.com/f8091adf49b284d61ae7de8bd9819e16
Drawback: Higher sampling cost
The cost of SPAR is about 10∼16 (resp. 2.5∼4) times of 2D-RS under strong (resp. weak) adversaries
STARK-proving low-degree-ness of a data availability root: some analysis Vitalik, 2019.9
STARK proving that the extended Merkle root is correct
FRI as erasure code fraud proof
Related: Accumulator
Threshold voting
Simple honest-majority collation availability proof 2018.2
$ n/2BLS signature
Scalable honest-majority collation availability 2018.3
The above BLS scheme with erasure codes
Honest-majority availability votes across all shards for just the bandwidth cost of a single shard
Applications
Data availability engine
LazyLedger: A Distributed Data Availability Ledger With Client-Side Smart Contracts
Mustafa Al-Bassam
A data availability blockchain with sub-linear full block validation @ethresearch
Related On-chain Plasma
With fraud-proof-free data availability proofs, we can have scalable data chains without committees @ethresear.ch, Vitalik
Related: On-Chain Non-Interactive Data Availability Proofs by John Adler
Sharding
Proof of Custody
Formalizing and improving eth2’s approach toward finalization of invalid shard blocks Vitalik, 2019.10
Towards Solving the Data Availability Problem for Sharded Ethereum
Daniel Sel, Kaiwen Zhang, Hans-Arno Jacobsen (Technical University of Munich, Middleware Systems Research Group, etc.)
Unsolved Problems in Blockchain Sharding Medium by NEAR
Layer2
The Dawn of Hybrid Layer 2 Protocols
Plasma
Erasure coding (Reed-Solomon) for Plasma data availability @ethresearch
Plasma XT @ethresearch
Data Availability problem in implementing Plasma design @Medium by Onther
Tutorials
Vitalik on data availability proofs Video @StarkWare Sessions 2019
#Layer1 #Layer_2 #Ethereum_2.0